1. Field of the Invention
The present invention relates to a technique for lossless- or lossy-encoding image data for respective tiles.
2. Description of the Related Art
Upon categorizing image data based on the criteria of resolution and tone characteristics, they are roughly categorized into text (character)-based images which place importance on a high resolution, natural image-based images (image such as natural image) which place an importance on tone expression, and graphics-based images which place an importance on the balance between both criteria.
As will be described below, suitable encoding methods differ depending on the types (or attributes) of image data.
A text-based image is normally formed of two types of pixels from a local viewpoint even when image data is input as multi-valued data. For this reason, the text-based image is suited to lossless encoding compared to other types of images.
Put differently, since the image entropy is low, the text-based image is suited to lossless encoding. However, since the entropy is low, a slight deterioration often visually stands out. Therefore, a high-quality text-based image is required to be lossless-encoded.
By contrast, a natural image-based image normally has a high entropy (although it largely differs depending on objects). For this reason, if the natural image-based image is lossless-encoded, not so high compression ratio is expected. By applying encoding that allows deterioration of a visually inconspicuous part to the image of this type, a high compression ratio can be achieved. Such encoding is called lossy encoding as contrasted to the lossless encoding.
Therefore, a device which is required to attain high image quality adopts a method of compressing text-based image data by lossless encoding and natural image-based image data by lossy encoding.
On the frequency axis, deterioration in a higher-frequency range is hard to stand out compared to that in a lower-frequency range. In lossy encoding, it is a common practice to transform image data on a real space into frequency space data. As typical transformation, discrete cosine transformation (DCT) is known. Quantization processing required to reduce entropy is applied to the data transformed onto the frequency space. In this case, a quantization table has frequency dependence so that deterioration is suppressed as much as possible in the lower-frequency range, and it readily appears in the higher-frequency range. Finally, the quantized values undergo entropy-encoding using Huffman codes or the like.
Random noise is inevitably superposed on natural image data since the natural image data is generated by A/D-converting a signal photoelectrically converted by an image sensing element. Such random noise-superposed data is very ill-suited to lossless encoding.
By contrast, a computer graphics-based image (to be referred to as a CG image hereinafter) is basically free from any random noise, and is suited to lossless encoding in this respect. Meanwhile, a CG image includes sharp edges which are not included in a natural image, and is unsuited to the DCT transformation.
The types of CG images are infinite in variety, i.e., there are many types of CG images from those with a fewer number of tone levels to those with a larger number of tone levels. In an extreme case, a CS image approximate to a natural image can be generated. For this reason, it cannot be categorically described that CG images are always suited to lossless encoding. Therefore, CG images include those suited to lossless encoding, and those suited to lossy encoding.
Since the aforementioned discrete cosine transformation is arithmetic processing including multiplications of real number coefficients, many processes are required (e.g., quantized values must be re-arranged to a predetermined order before entropy encoding, and so forth) in addition to simple integer operations. For this reason, a lossy encoder often requires a larger hardware scale.
By contrast, lossless encoding does not require any real number operations, and can carry out processing using only integer values to the end. Also, lossless encoding does not require any re-arrangement of data as long as transformation onto the frequency space is not made, and the hardware scale can be simplified.
In recent years, in order to attain higher image quality of output devices such as printers and the like, output devices tend to have higher resolutions. Image data tend to have higher resolutions accordingly, and the resolution of an image which previously had been 600 dpi tends to rise up to 1200 dpi and to 2400 dpi.
This means that the capabilities required of software and hardware used to encode and decode image data rise to 4 times and 16 times.
A technique for lossless- or lossy-encoding image data in predetermined units such as blocks or tiles is known (for example, Japanese Patent Laid-Open No. 09-149260).
An overview of this technique can be expressed by an arrangement shown in FIG. 4. In the arrangement shown in FIG. 4, image data 401 scanned from an image scanner or generated by rendering page description language data is divided into tiles. A lossless encoding unit 403 and lossy encoding unit 405 parallelly apply encoding processing to one tile. A determination unit 407 determines based on code sizes generated by the respective encoding units and various parameters obtained during the encoding processes whether or not the image data is to be lossless- or lossy-encoded, and sends the determination result to a selection unit 409.
The selection unit 409 selects one of the two different types of encoded data output from the two encoding units based on the determination result, and stores the selected encoded image data in a memory 411. In this way, encoding of one tile is completed. Upon completion of encoding of all tile data for one page image, the encoded data of the page image are transferred to and stored in a hard disk drive 413 together.
The memory 411 is a so-called semiconductor memory, and can only hold encoded data for several to several tens of pages. On the other hand, since the hard disk drive 413 generally has a capacity of several hundred Gbytes nowadays, it can store encoded data for several tens of thousands of pages or more.
Also, an arrangement shown in FIG. 5 can be easily considered. In this arrangement, a determination unit 421 has a function of directly generating parameters required to determine lossless or lossy encoding from tile data. This determination unit 421 determines, based on the generated parameters, which encoded data is to be selected. The determination result is sent to a distribution unit 423, which supplies tile data to one of the lossless encoding unit 403 and lossy encoding unit 405, and controls the selected encoding unit to encode the tile data. As a result, since one of the two encoding units outputs encoded data, encoding of that tile data is completed when that encoded data is stored in the memory 411.
In either of the arrangements shown in FIGS. 4 and 5, in order to encode arbitrary image data within a predetermined period of time (to be referred to as “Tone page time period” hereinafter), each of the two encoding units must have capability to encode all image data for one page within one page time period.
Assuming that one encoding unit is used at a capacity usage ratio of 85% to encode all image data with a resolution of 600 dpi within one page time period, image data with a resolution of 1200 dpi has a fourfold data size. For this reason, encoding must be done by parallelly operating the four encoding units. Furthermore, since an image with a resolution of 2400 dpi has a 16-fold data size, its encoding process cannot be completed within one page time period unless 14 to 16 encoding units are parallelly operated. In case of the 14 encoding units, encoding processing can be done within one page time period if each encoding unit is operated at a capacity usage ratio of 16×0.85/14×100 (%)≈97.1 (%) or higher.
As described above, conventionally, encoding must be done by parallelly operating many encoding units to encode image data with higher resolutions in large quantities, resulting in a huge circuit scale of the encoding units. Therefore, high cost is required to manufacture that encoding apparatus.
In order to reduce the hardware scale, the degree of parallelism of lossy encoding units to be parallelly operated is lowered. However, when the degree of parallelism is lowered, the capability of each lossy encoding unit drops, and the lossy encoding processing cannot be completed within a predetermined period of time, thus posing another problem.